class Solution {
public:
    // int deleteAndEarn(vector<int>& nums) {
    //     sort(nums.begin(), nums.end());

    //     unordered_map<int, int> mymap;
    //     for (auto& i : nums)
    //         mymap[i]++;

    //     vector<int> dp(mymap.size() + 2);
    //     //初始化dp表
    //     dp[2] = nums[0] * mymap[nums[0]];

    //     int index = 3;
    //     for (int i = 1; i < nums.size(); i++)
    //     {
    //         if (nums[i] == nums[i - 1])
    //             continue;
    //         else
    //         {
    //             if (nums[i] - nums[i - 1] == 1)
    //                 dp[index] = max(dp[index - 3], dp[index - 2]) + nums[i] * mymap[nums[i]];
    //             else
    //                 dp[index] = max(dp[index - 2], dp[index - 1]) + nums[i] * mymap[nums[i]];

    //             index++;
    //         }
    //     }

    //     return max(dp[mymap.size() + 1], dp[mymap.size()]);
    // }

    //方法二：
    //利用一个数组，数组的下标对应的位置就是下标值对应的元素出现的总和
    int deleteAndEarn(vector<int>& nums) {
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] > max)
                max = nums[i];
            if (nums[i] < min)
                min = nums[i];
        }

        int range = max - min + 1;
        vector<int> arr(range);
        for (auto e : nums)
            arr[e - min] += e;

        //处理特殊情况
        if (range == 1)
            return arr[0];
        if (range == 2)
            return std::max(arr[0], arr[1]);

        //将arr数组视为dp表
        //初始化dp表：
        arr[2] += arr[0];

        for (int i = 3; i < range; i++)
            arr[i] += std::max(arr[i - 3], arr[i - 2]);

        return std::max(arr[range - 1], arr[range - 2]);
    }
};